package train48days;
import java.util.*;

class SubTree{
    public SubTree(String pre,String post){
        this.pre = pre;
        this.post = post;
    }
    String pre;
    String post;
}
public class Pre_Post {
    //计算阶乘
    public static  long fac(int n){
        long f = 1;
        for(int i = 1;i <= n;i++){
            f *= i;
        }
        return f;
    }
    //计算C n m
    public static long calcCom(int n,int m){
        m = m < (n - m)? m : (n - m);
        long r = 1;
        for(int i = n;i >= n - m + 1;i--){
            r *= i;
        }
        return r / fac(m);
    }
    public static List<SubTree> calcSubTree(String prev,String post){
        //子树的根在前序遍历结果中的位置
        int subRootPreIdx = 1;
        //后序遍历
        int postFirst = 0;
        List<SubTree> subTreeList = new ArrayList<>();
        while(subRootPreIdx < prev.length()){
            //确认该棵子树的根节点
            char rootSub = prev.charAt(subRootPreIdx);
            int subRootPostIdx = post.indexOf(rootSub);
            int subTreeNodeCount = subRootPostIdx - postFirst + 1;
            //从前序和后续遍历结果中分离出该棵子树的前序和后序遍历结果
            SubTree subTree = new SubTree(
                    prev.substring(subRootPreIdx,subRootPreIdx + subTreeNodeCount),
                    post.substring(postFirst,postFirst + subTreeNodeCount)
            );
            subTreeList.add(subTree);
            //继续分离下一棵子树
            subRootPreIdx += subTreeNodeCount;
            postFirst += subTreeNodeCount;
        }
        return subTreeList;
    }
    public static long CalcTreePossible(int m,String pre,String post){
        if(pre.isEmpty() || pre.length() == 1){
            return 1;
        }
        //先分离出根节点有多少棵树
        List<SubTree> subTree =  calcSubTree(pre,post);
        //根节点子树可能性的组合结果
        long result = calcCom(m,subTree.size());
        //根的子树有多少种可能性
        for(SubTree e : subTree){
            result *= CalcTreePossible(m,e.pre,e.post);
        }
        return result;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int m = in.nextInt();
            if(m == 0){
                break;
            }
            //接收子树的前序和后续遍历结果
            String pre = in.next();
            String post = in.next();

            System.out.println(CalcTreePossible(m,pre,post));
        }
    }
}
